import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 马拉圈
 * Date: 2023-05-07
 * Time: 22:44
 */
public class UnionFindSet {
    public int[] elem;


    public UnionFindSet(int n) {
        this.elem = new int[n];
        Arrays.fill(this.elem, -1);
    }

    //找x这个节点所在集合 ---> 所在树 ---> 树的根节点下标
    //默认x节点的值跟下标一致
    //一般是有【 x = ki + b 】的关系
    //这一点只需要在传参的时候转化为下标即可
    //对于特殊情况，可以用map对每个节点安排下标！ 下面的代码不考虑~
    public int findRoot(int x) {
        if(x < 0) {
            throw new IndexOutOfBoundsException("下标为负数");
        }
        while(elem[x] >= 0) {
            x = elem[x];
        }
        return x;
    }

    //合并x1和x2
    //设x1任然是根节点，x2连接到x1下
    public void union(int x1, int x2) {
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if(index1 == index2) {
            return;//同一棵树
        }else {
            elem[index1] += elem[index2];
            elem[index2] = index1;
        }
    }

    //判断是否在一个集合内
    public boolean isSameSet(int x1, int x2) {
        return findRoot(x1) == findRoot(x2);
    }

    //计算集合的个数
    public int getSetCount() {
        int count = 0;
        for(int x : elem) {
            if(x < 0) {
                count++;
            }
        }
        return count;
    }

    public void display() {
        for(int x : elem) {
            System.out.print(x + " ");
        }
        System.out.println();
    }

    //根据需求得到下标
    public int getIndexByX(int x) {
        return x;
    }

    //获得省份数量
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFindSet unionFindSet = new UnionFindSet(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if(isConnected[i][j] == 1) {
                    unionFindSet.union(i, j);
                }
            }
        }
        return unionFindSet.getSetCount();
    }
    public int getIndexByX(char x) {
        return x - 'a';
    }
    //等式方程可满足性

    public boolean equationsPossible(String[] equations) {
        UnionFindSet unionFindSet = new UnionFindSet(26);
        for(String str : equations) {
            if(str.charAt(1) == '=') {
                char ch1 = str.charAt(0);
                char ch2 = str.charAt(3);
                unionFindSet.union(getIndexByX(ch1), getIndexByX(ch2));
            }
        }
        for(String str : equations) {
            if(str.charAt(1) == '!') {
                char ch1 = str.charAt(0);
                char ch2 = str.charAt(3);
                if(unionFindSet.isSameSet(getIndexByX(ch1), getIndexByX(ch2))) {
                    return false;
                }
            }
        }
        return true;
    }

}
